package LeetCode;
/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 思路：以中间为轴【找中间节点（876）】--反转中间节点之后的子链表2（206）--比较2与原链表，2走到null都相同则是回文
 */
public class Num234 {
    /**
     * 方法1：以中间为轴【找中间节点（876）】--反转中间节点之后的子链表2（206）--比较2与原链表，2走到null都相同则是回文
     * @param head
     * @return
     */
//    public ListNode midNode(ListNode head){
//
//        //找中间节点
//        ListNode fast=head;
//        ListNode slow=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//    public ListNode reverse(ListNode head) {
//        //反转链表
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode node=head;//待处理节点
//        ListNode prev=null;//待处理节点的前驱
//        while (node!=null){
//            ListNode next=node.next;//待处理节点的下一个节点暂存在next
//            node.next=prev;
//            prev=node;
//            node=next;
//        }
//        return prev;
//    }
//    public boolean isPalindrome(ListNode head) {
//        //1.找到中间节点
//        ListNode midList=midNode(head);
//        //2.反转中间节点后的子链表
//        ListNode s=reverse(midList);
//        //3.同时遍历原先链表s1与子链表s【s1不用拆】
//        while(s!=null){
//            if(s.val!=head.val){
//                return false;
//            }
//            head=head.next;
//            s=s.next;
//        }
//        return true;
//    }

    /**
     * 方法2：创建新链表，边新遍历边头插让新链表是原来的反转链表；链表与原链表比较
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode node=reverse(head);
        while(head!=null){
            if(node.val!= head.val){
                return false;
            }
            head=head.next;
            node=node.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        //创建一个新链表给它插入值【头插】
        ListNode newHead=null;
        while(head!=null){
            ListNode node=new ListNode(head.val);
            node.next=newHead;
            newHead=node;
            head=head.next;
        }
        return newHead;
    }

}
